package bsh;

import java.util.ArrayList;
import java.util.List;

import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;

import bsh.exception.CompilationFailedException;
import bsh.meta.JavaClassWrapper;
import bsh.meta.Scope;
import bsh.meta.ScopeType;
import bsh.meta.TypeWrapper;

/**
 * {@link NodeCompiler} for {@link BSHSwitchStatement}
 * 
 * @author takeshi
 */
public class SwitchNodeCompiler implements NodeCompiler {

    private final BSHSwitchStatement node;

    /**
     * C'tor
     * 
     * @param node the node to compile
     */
    public SwitchNodeCompiler(BSHSwitchStatement node) {
        super();
        this.node = node;
    }

    /**
     * {@inheritDoc}
     */
    public void compile(MethodVisitor host, CompilationState state) throws CompilationFailedException {
        int stack = state.getStackSize();
        state.getUnit().compileNode(this.node.getChild(0), host, state);
        state.assertStackSize(stack + 1);
        state.getUnit().getCompilerManager().coerceStackTopTo(host, JavaClassWrapper.INT_WRAPPER, state);
        state.assertStackSize(stack + 1);
        Scope scope = state.newScope(ScopeType.LOOP_BLOCK); // we call it a loop
                                                            // so break exits
                                                            // out of it
        scope.installStartLabel(host, state.getUnit().options());
        SwitchLabel[] allCases = readAllSwitchLabels();
        SwitchLabel defaultCase = defaultSwitchCase(allCases);
        int[] caseValues = readValues(allCases, defaultCase != null);
        Label[] labels = caseLabels(allCases, defaultCase != null);
        sortSwitchCaseValues(caseValues, labels);
        host.visitLookupSwitchInsn(defaultCase == null ? scope.getEndLabel() : defaultCase.label, caseValues, labels);
        state.popStack();
        for (SwitchLabel currentCase : allCases) {
            host.visitLabel(currentCase.label);
            for (int i = currentCase.nodeIndex + 1; i < this.node.jjtGetNumChildren() && !(this.node.getChild(i) instanceof BSHSwitchLabel); i++) {
                stack = state.getStackSize();
                state.getUnit().compileNode(this.node.getChild(i), host, state);
                if (stack != state.getStackSize()) {
                    state.popStack(host);
                }
            }
        }
        scope.installEndLabel(host, state.getUnit().options());
    }

    /**
     * Merge-sorts the caseValues, also moving the sort labels along
     * 
     * @param caseValues the case values
     * @param labels the corresponding labels
     */
    private static void sortSwitchCaseValues(int[] caseValues, Label[] labels) {
        msort(caseValues, labels, 0, labels.length);
    }

    /**
     * Recursively merge-sorts the case values, from left to right (exclusive)
     * 
     * @param caseValues the case values to be sorted
     * @param labels the labels
     * @param left the beginning index
     * @param right the end index (exclusive)
     */
    private static void msort(int[] caseValues, Label[] labels, int left, int right) {
        if (left >= right - 1) {
            // already sorted
            return;
        }
        int mid = (right + left) / 2;
        msort(caseValues, labels, left, mid);
        msort(caseValues, labels, mid, right);
        merge(caseValues, labels, left, mid, right);
    }

    /**
     * Merges two consecutive sorted sections of the caseValues arrays, also sorting the labels array
     * 
     * @param caseValues the caseValues to be sorted
     * @param labels the corresponding labels
     * @param left the beginning index of the left segment
     * @param mid the end index (exclusive) of the left segment and also the beginning index of the right segment
     * @param right the end index of the right segment
     */
    private static void merge(int[] caseValues, Label[] labels, int left, int mid, int right) {
        int[] ri = new int[right - left];
        Label[] rl = new Label[right - left];
        int i = left, j = mid;
        int n = 0;
        while (i < mid && j < right) {
            if (caseValues[i] < caseValues[j]) {
                ri[n] = caseValues[i];
                rl[n++] = labels[i++];
            } else {
                ri[n] = caseValues[j];
                rl[n++] = labels[j++];
            }
        }
        while (i < mid) {
            ri[n] = caseValues[i];
            rl[n++] = labels[i++];
        }
        while (j < right) {
            ri[n] = caseValues[j];
            rl[n++] = labels[j++];
        }
        System.arraycopy(ri, 0, caseValues, left, ri.length);
        System.arraycopy(rl, 0, labels, left, rl.length);
    }

    /**
     * Creates the labels for all the cases
     * 
     * @param allCases the cases
     * @param hasDefault if this switch statement has a default case
     * @return array of {@link Label}
     */
    private static Label[] caseLabels(SwitchLabel[] allCases, boolean hasDefault) {
        Label[] result = new Label[hasDefault ? allCases.length - 1 : allCases.length];
        for (int i = 0, j = 0; j < allCases.length; j++) {
            if (!allCases[j].isDefault()) {
                result[i++] = allCases[j].label;
            }
        }
        return result;
    }

    /**
     * Reads all the case values of the given cases
     * 
     * @param allCases the cases
     * @param hasDefault if there is a default case
     * @return array of int
     */
    private static int[] readValues(SwitchLabel[] allCases, boolean hasDefault) {
        int[] result = new int[hasDefault ? allCases.length - 1 : allCases.length];
        for (int i = 0, j = 0; j < allCases.length; j++) {
            if (!allCases[j].isDefault()) {
                result[i++] = allCases[j].caseNumber();
            }
        }
        return result;
    }

    /**
     * Returns the default case if there is any
     * 
     * @param allCases all the cases
     * @return {@link SwitchLabel}
     */
    private static SwitchLabel defaultSwitchCase(SwitchLabel[] allCases) {
        for (SwitchLabel switchLabel : allCases) {
            if (switchLabel.isDefault()) {
                return switchLabel;
            }
        }
        return null;
    }

    /**
     * Reads all swithLabels from the {@link BSHSwitchStatement} node.
     * 
     * @return array of {@link SwitchLabel}
     * @throws CompilationFailedException e
     */
    private SwitchLabel[] readAllSwitchLabels() throws CompilationFailedException {
        List<SwitchLabel> list = new ArrayList<SwitchNodeCompiler.SwitchLabel>(this.node.jjtGetNumChildren());
        for (int i = 1; i < this.node.jjtGetNumChildren(); i++) {
            if (node.jjtGetChild(i) instanceof BSHSwitchLabel) {
                list.add(parseLabel(i, (BSHSwitchLabel) node.getChild(i)));
            }
        }
        return list.toArray(new SwitchLabel[list.size()]);
    }

    /**
     * Parses a {@link BSHSwitchLabel}.
     * 
     * @param index the index of the given {@link BSHSwitchLabel} in the {@link BSHSwitchStatement}
     * @param child the node to parse
     * @return {@link SwitchLabel}
     * @throws CompilationFailedException e
     */
    private static SwitchLabel parseLabel(int index, BSHSwitchLabel child) throws CompilationFailedException {
        if (child.isDefault) {
            return new DefaultSwitchCase(index);
        }
        int caseValue = findLiteralIntegerValue(child.getChild(0));
        return new SwitchCase(index, caseValue);
    }

    /**
     * Tries to find the literal integer value of a given node. Recurses into nodes with only one child, which may lead to weird things
     * 
     * @param child the node
     * @return int
     * @throws CompilationFailedException e
     */
    private static int findLiteralIntegerValue(SimpleNode child) throws CompilationFailedException {
        if (child instanceof BSHLiteral) {
            Object value = Primitive.unwrap(((BSHLiteral) child).value);
            if (value instanceof Integer || value instanceof Short || value instanceof Byte) {
                return ((Number) value).intValue();
            } else if (value instanceof Character) {
                return ((Character) value).charValue();
            }
            throw new CompilationFailedException(child.getLineNumber(), "Expected integer literal, but was: " + value);
        } else if (child.jjtGetNumChildren() == 1) {
            return findLiteralIntegerValue(child.getChild(0));
        } else {
            throw new CompilationFailedException(child.getLineNumber(), "Expected integer literal, but was: " + child);
        }
    }

    /**
     * {@inheritDoc}
     */
    public TypeWrapper nodeResultType(Scope scope) throws CompilationFailedException {
        return JavaClassWrapper.VOID_WRAPPER;
    }

    /**
     * Represents a switch case label - can be a default case
     * 
     * @author takeshi
     */
    private abstract static class SwitchLabel {
        private final Label label = new Label();

        private final int nodeIndex;

        /**
         * C'tor
         * 
         * @param nodeIndex the node index of this label
         */
        public SwitchLabel(int nodeIndex) {
            super();
            this.nodeIndex = nodeIndex;
        }

        /**
         * @return true if this is a default case
         */
        abstract boolean isDefault();

        /**
         * @return the literal value of this case
         */
        abstract int caseNumber();
    }

    /**
     * A regular switch case
     * 
     * @author takeshi
     */
    private static class SwitchCase extends SwitchLabel {
        private final int caseValue;

        /**
         * C'tor
         * 
         * @param nodeIndex the node index
         * @param caseValue the case value
         */
        public SwitchCase(int nodeIndex, int caseValue) {
            super(nodeIndex);
            this.caseValue = caseValue;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        boolean isDefault() {
            return false;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        int caseNumber() {
            return caseValue;
        }

    }

    /**
     * A default switch case
     * 
     * @author takeshi
     */
    private static class DefaultSwitchCase extends SwitchLabel {

        /**
         * @param nodeIndex the node index
         */
        public DefaultSwitchCase(int nodeIndex) {
            super(nodeIndex);
        }

        /**
         * {@inheritDoc}
         */
        @Override
        boolean isDefault() {
            return true;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        int caseNumber() {
            throw new IllegalArgumentException();
        }

    }

}
